백준 7576번
오늘 풀어본 문제는 백준의 7576번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 $M$, $N$이 주어진다. $M$은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, $2 \leq M,N \leq 1,000$ 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 $N$개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 $M$개의 정수로 주어진다. 정수 $1$은 익은 토마토, 정수 $0$은 익지 않은 토마토, 정수 $-1$은 토마토가 들어있지 않은 칸을 나타낸다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
출력
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 $0$을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 $-1$을 출력해야 한다.
풀이과정
어떤 익은 토마토에 전후좌후로 붙어있는 토마토들이 하루가 지나면 익는다고 되어있다. 각 토마토가 서로 붙어있는 모습을 그래프처럼 생각한다면, 그래프에서 노드 하나를 방문할 때 마다 하루가 지난다고 생각할 수 있다.
이 점을 이용해서, 전후좌후의 토마토 중 방문하지 않은 토마토를 방문하고, 이 토마토의 위치 정보에 거쳐온 ‘스텝 수’를 끼워넣어 큐에 저장하는 방식을 생각해보았다.
큐가 텅 빌 떄까지 반복하면서, 가장 큰 ‘스텝 수’를 저장하고, 이것을 걸린 일수로 생각하였다. 큐가 비게 되면, 모든 토마토를 검사하여 만약 익지 않은 토마토가 있다면 $-1$을 출력하도록 하고, 모든 토마토가 익었다면 그 ‘스텝 수’를 출력하도록 하였다.
첫 번째 시도
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int tomatoes[1000][1000] = { 0, };
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int width, height, tempTomato;
int timePassed = 0;
pair<pair<int, int>, int> currentRipenTomato;
queue<pair<pair<int, int>, int>> ripenTomatoes;
cin >> width >> height;
for (int j = 0; j < height; j++) {
for (int i = 0; i < width; i++) {
cin >> tempTomato;
tomatoes[i][j] = tempTomato;
if (tempTomato == 1) {
ripenTomatoes.push({ {i, j}, 0 });
}
}
}
while (!ripenTomatoes.empty()) {
currentRipenTomato = ripenTomatoes.front();
ripenTomatoes.pop();
if (timePassed < currentRipenTomato.second) {
timePassed = currentRipenTomato.second;
}
pair<int, int> currentRipenTomatoPosition = currentRipenTomato.first;
if (currentRipenTomatoPosition.first > 0 && tomatoes[currentRipenTomatoPosition.first - 1][currentRipenTomatoPosition.second] == 0) {
pair<int, int> newRipenTomatoPosition = { currentRipenTomatoPosition.first - 1, currentRipenTomatoPosition.second };
tomatoes[newRipenTomatoPosition.first][newRipenTomatoPosition.second] = 1;
ripenTomatoes.push({ newRipenTomatoPosition, currentRipenTomato.second + 1 });
}
if (currentRipenTomatoPosition.first < width - 1 && tomatoes[currentRipenTomatoPosition.first + 1][currentRipenTomatoPosition.second] == 0) {
pair<int, int> newRipenTomatoPosition = { currentRipenTomatoPosition.first + 1, currentRipenTomatoPosition.second };
tomatoes[newRipenTomatoPosition.first][newRipenTomatoPosition.second] = 1;
ripenTomatoes.push({ newRipenTomatoPosition, currentRipenTomato.second + 1 });
}
if (currentRipenTomatoPosition.second > 0 && tomatoes[currentRipenTomatoPosition.first][currentRipenTomatoPosition.second - 1] == 0) {
pair<int, int> newRipenTomatoPosition = { currentRipenTomatoPosition.first, currentRipenTomatoPosition.second - 1 };
tomatoes[newRipenTomatoPosition.first][newRipenTomatoPosition.second] = 1;
ripenTomatoes.push({ newRipenTomatoPosition, currentRipenTomato.second + 1 });
}
if (currentRipenTomatoPosition.second < height - 1 && tomatoes[currentRipenTomatoPosition.first][currentRipenTomatoPosition.second + 1] == 0) {
pair<int, int> newRipenTomatoPosition = { currentRipenTomatoPosition.first, currentRipenTomatoPosition.second + 1 };
tomatoes[newRipenTomatoPosition.first][newRipenTomatoPosition.second] = 1;
ripenTomatoes.push({ newRipenTomatoPosition, currentRipenTomato.second + 1 });
}
}
for (int j = 0; j < height; j++) {
for (int i = 0; i < width; i++) {
if (tomatoes[i][j] == 0) {
timePassed = -1;
break;
}
}
if (timePassed == -1) {
break;
}
}
cout << timePassed;
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
이번에 문제를 풀면서 로컬에서 계속 문제가 있었다. 인접한 토마토를 방문하는 것이 아닌, 전혀 뜬금없는 토마토를 방문하는 모습을 확인할 수 있었다. 그리고 어느 시점에서 제대로 토마토를 탐색하지 못하고 무한루프에 빠지게 되었다.
코드를 수차례 다시 확인해본 결과, 변수명을 잘못 입력했다는 것을 알게되었다. 변수 이름 2개가 비슷해서 이를 혼동한 것이다.
내가 쓴 PS 글들의 코드를 읽어보면 알겠지만, 내가 코드에서 변수명을 길게 짓는다는 것을 확인할 수 있을 것이다. 이건 Clean Code 라는 책에서 읽은 방법 중 변수 명이 무엇을 의미하는지 바로 이해할 수 있도록 돕기 위한 방안이었는데, PS도 적용해보면 어떨까 싶어 시도해본 방법이었다.
그런데 오늘, 그 방법의 단점을 알게된 것이다. 비슷한 변수명의 경우 틀려도 눈치채기 힘들 수 있다는 것이다. 그 외에도 변수 이름을 짓는데 골치를 앓는 등의 문제는 있어왔지만, 오늘 같은 경우는 거의 없었다. 그래서 앞으로 변수명을 지을 때, 이 기준을 조금 완화하는 편이 좋을 것 같다. 이번 일은 Clean Code 를 잘못 적용한 사례 중 하나로 생각할 수 있을 것 같다. (애초에 clean 한 code 처럼 보이지는 않는다.)
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/7576